/** 斐波那契数；O(n)
 * 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。
 * 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
 * 也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。
 * @param n
 * @returns
 */
export const fib = (n: number): number => {
  const dp: number[] = new Array(n + 1).fill(0); //dp数组初始化
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]; //递推公式
  }
  return dp[n];
};

/** 使用最小花费爬楼梯
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
 * @param cost
 * @returns
 */
export function minCostClimbingStairs(cost: number[]): number {
  const dp = [0, 0];
  for (let i = 2; i <= cost.length; i++) {
    dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  }
  console.log(dp);
  return dp[cost.length];
}

export function uniquePaths(m: number, n: number): number {
  // const dp1: number[][] = new Array(m).fill(0).map((_) => []);
  const dp: number[][] = new Array(m).fill(1).map(() => new Array(n).fill(1));
  //   for (let i = 0; i < m; i++) {
  //     dp[i][0] = 1;
  //   }
  //   for (let i = 0; i < n; i++) {
  //     dp[0][i] = 1;
  //   }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

export const Solution = (m: number, n: number): number => {
  let numerator = 1; //# 分子
  let denominator = m - 1; //# 分母
  let count = m - 1; //# 计数器，表示剩余需要计算的乘积项个数
  let t = m + n - 2; //# 初始乘积项
  while (count > 0) {
    numerator *= t; //# 计算乘积项的分子部分
    t--; //# 递减乘积项
    while (denominator != 0 && numerator % denominator == 0) {
      numerator /= denominator; //# 约简分子
      denominator--;
    }
    count--;
  }
  return numerator; //# 返回最终的唯一路径数
};

export function integerBreak(n: number): number {
  /**
        dp[i]: i对应的最大乘积
        dp[2]: 1;
        ...
        dp[i]: max(
            1 * dp[i - 1], 1 * (i - 1),
            2 * dp[i - 2], 2 * (i - 2),
            ..., (i - 2) * dp[2], (i - 2) * 2
        );
     */
  const dp: number[] = new Array(n + 1).fill(0);
  dp[2] = 1;
  for (let i = 3; i <= n; i++) {
    for (let j = 1; j <= i / 2; j++) {
      dp[i] = Math.max(dp[i], j * dp[i - j], j * (i - j));
    }
  }
  return dp[n];
}

/** 背包重量规划；
 * 背包理论01，滚动数组
 * @param weight 重量数组
 * @param value 价值数组
 * @param size 背包容量
 * @returns 最大价值
 */
export function weightBagProblem(
  weight: number[],
  value: number[],
  size: number
): number {
  const goodsNum: number = weight.length;
  const dp: number[] = new Array(size + 1).fill(0);
  for (let i = 0; i < goodsNum; i++) {
    //i是物品
    for (let j = size; j >= weight[i]; j--) {
      //j是背包容量
      dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
  }
  return dp[size];
}

/** 完全平方数
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。
 * 你需要让组成和的完全平方数的个数最少。
 * @param n
 * @returns
 */
export function numSquares(n: number): number {
  const goodsNum: number = Math.floor(Math.sqrt(n));
  const dp: number[] = new Array(n + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= goodsNum; i++) {
    const tempVal: number = i * i;
    for (let j = tempVal; j <= n; j++) {
      dp[j] = Math.min(dp[j], dp[j - tempVal] + 1);
    }
  }
  return dp[n];
}

/** 打家劫舍；时间复杂度: O(n)
 * 你是一个专业的小偷，计划偷窃沿街的房屋。
 * 每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统。
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * @param nums
 * @returns 偷窃到的最高金额
 */
export function rob(nums: number[]): number {
  /**
        dp[i]: 前i个房屋能偷到的最大金额
        dp[0]: nums[0];
        dp[1]: max(nums[0], nums[1]);
        ...
        dp[i]: max(dp[i-1], dp[i-2]+nums[i]);
     */
  const length: number = nums.length;
  if (length === 1) return nums[0];
  const dp: number[] = [];
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[length - 1];
}

/** 判断子序列
 * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 * @param s
 * @param t
 * @returns
 */
export function isSubsequence(s: string, t: string): boolean {
  /**
        dp[i][j]: s的前i-1个，t的前j-1个，最长公共子序列的长度
     */
  const sLen: number = s.length,
    tLen: number = t.length;
  const dp: number[][] = new Array(sLen + 1)
    .fill(0)
    .map((_) => new Array(tLen + 1).fill(0));
  for (let i = 1; i <= sLen; i++) {
    for (let j = 1; j <= tLen; j++) {
      if (s[i - 1] === t[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[sLen][tLen] === s.length;
}

/** 最长回文子序列
 *
 * @param s
 * @returns
 */
export function longestPalindromeSubseq(s: string): number {
  /**
        dp[i][j]：[i,j]区间内，最长回文子序列的长度
     */
  const length: number = s.length;
  const dp: number[][] = new Array(length)
    .fill(0)
    .map((_) => new Array(length).fill(0));
  for (let i = 0; i < length; i++) {
    dp[i][i] = 1;
  }
  // 自下而上，自左往右遍历
  for (let i = length - 1; i >= 0; i--) {
    for (let j = i + 1; j < length; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
      }
    }
  }
  return dp[0][length - 1];
}

const weight = [1, 4, 3];
const price = [15, 30, 20];
